1. Field of the Invention
This invention relates generally to communication techniques and, more particularly, to the decoding of digital signals in a communication system. In the communication system envisioned by the present invention, each bit of information has been encoded in a multiplicity of transmitted signals. The resulting signals are generally referred to as convolutionally encoded symbols.
2. Description of the Related Art
Communications channels in general and digital wireless communications in particular must counteract noise which may obliterate individual transmitted symbols. Conceptually, there are two approaches to this problem: one, by introducing redundancy and another, by smearing the transmitted information over multiple symbols. These approaches are not entirely separate since any redundancy makes it easier to spread the information over a plurality of signals, but neither are the two approaches identical.
Convolution codes are often used to implement the smearing of information over several symbols. Simply put, the EXCLUSIVE_OR (XOR) logic operation is applied to several recent information bits (equivalently, the information bits are summed modulo 2) to generate a bit that is to be transmitted. A second or third convolution code can be used to generate a second or third bit and thereby introduce redundancy as well as the information smearing in the transmitted symbols. These several bits are often combined and transmitted as a single symbol, represented perhaps by one state of a modulation constellation.
Referring to FIG. 1, an example of channel coding used for IS-95 is illustrated. The IS-95 encoder 10 has a series of delay line components 11. A first set of selected signals from the terminals of the delay line components 11 are applied to a first XOR component 12, while a second set of selected signals from the terminals of the delay line components are applied to a second XOR component 14. This rate xc2xd code has constraint length 9, i.e. 9 delay line components 11. Notice that for this encoder, each input bit results in two different output bits and that each of the two output bits depends on the current input bit and either four or five of the preceding eight input bits. Assuming that the preceding eight bits are fixed, there are only two output bit-pairs possible from XOR components 12, 14 depending upon the next input bit. However, there are four possible output bit-pairs that could be transmitted in all when the preceding bits are not fixed.
Note that, for the exemplary IS-95 channel encoder, a single input bit affects the next 9 output bit pairs, no one of which reflects exactly the information of that single input bit. The convolution codes smear the information of the single input bit over eighteen bits of output bit pairs. The virtue of this smearing of information is that, when a single symbol (or even more than one symbol) is corrupted in transmission, the decoder often can still recover the input information bit.
Computing Metrics
Pairs of output bits become symbols that have some physical representation on the communications channel. These symbols are transmitted and the receiver makes a measurement of the resulting signal that it receives. Of course, the received signal differs from the signal that is transmitted and the difference between the two signals is called noise. The receiver can calculate the distance between the received signal and each of the four symbols that might have been transmitted. The details of the computation of this metric depend on the particular communications channel and how the states are represented physically.
In the receiver""s computation of metrics, a first option provides for the conversion of the received signal to a digital signal (in this case a pair of bits) and then computation of the metric. Apparatus using this approach is called a hard decision decoder. The other option, which is more complex computationally but which generally results in fewer errors, is the computation of the metric from the original signal levels; this process being provided by a soft decision decoder.
Trellis Decoding
Referring next to FIG. 2, a four-state trellis diagram, according to the prior art, is illustrated. Each column of the trellis diagram represents a Viterbi decoder at an instant of time and the arrows in the diagram represent the transitions of that decoder from one instant of time to the next. Notice that the nodes of the diagram are labeled with a pair of binary digits, 00, 01, 10, 11, the binary digits representing the state numbers 0, 1, 2, and 3. Also observe that the arrows between nodes are labeled either 0 or 1 and that the label of each node is always formed by concatenating the labels any pair of arrows from two columns earlier that lead to that node. Expressed another way, the number of each node specifies the last two (because this is a four-state decoder) transitions made to get to that state. Of course multiple paths lead to each state, but these paths differ only at earlier transitions.
Referring once again to FIG. 2, in moving from one increment of time to the next, the Viterbi decoder, i.e., a decoder that decodes convolutionally encoded symbols, receives or computes metrics representing the distance from the received signal to what would be transmitted for an information bit of xe2x80x9c0xe2x80x9d and for an information bit of xe2x80x9c1xe2x80x9d. This computation is performed for each possible history of transmitted bits as encoded by the various state identification numbers. These metrics are referred to as transition metrics and they include the noise for a current symbol. The transition metrics are summed along the paths and these sums are called path metrics.
Two arrows represent transitions that can enter each node and two other arrows represent transitions that can leave each node. At each node, path metrics are associated with each incoming arrow. The trellis decoder selects the smaller path metric, i.e., the path metric representing the smaller noise figure of the two incoming signals. All of the paths associated with the non-selected arrow (i.e., transition) are permanently abandoned by the trellis decoder. The transition metric corresponding to an information bit of xe2x80x9c1xe2x80x9d is added to the surviving incoming path metric and the sum is forwarded to the node at the next time instant along the arrow labeled 1. Similarly, the transition metric corresponding to an information bit of 0 is added to the surviving incoming path metric and sent to the node at the next time instant along the arrow labeled 0. The configuration of two incoming arrows and the two outgoing arrows from a node can be described as a butterfly diagram.
Referring to FIG. 3, examples of butterfly diagrams are shown for a 16-state encoder. For each butterfly diagram, two states serve as input transitions to determine two states for the next time increment. For example, for the butterfly diagram represented by the solid lines, the states 0001 and 1001 serve as inputs to the determine the states 0100 and 0011 for the next time increment. Unfortunately, a significant amount of memory is needed to specify each state. In implementing the decoding algorithm, not only is the history information associated with each state retained, but the path metrics are also retained, i.e., for selecting between two input transitions that terminate on the same state. If the butterfly operations are processed as indicated in FIG. 3, two copies of these data groups would be required to be saved in order that the storage resulting from one butterfly diagram does not corrupt the input data needed to process the result of a different butterfly diagram.
An alternative to the doubling of the required memory is to re-assign the state table at each iteration as illustrated in FIG. 4. Note also in FIG. 4, at each stage, the butterfly operation is applied in a quite regular fashion, the pattern merely changes from one time increment to the next time increment. Specifically, the height of the butterfly transition is constant within each stage, but reduces by half from one stage to the next stage.
The primary, but not sole advantage to re-arranging the order of the state memories is that, as the data for a state is updated, the new data can be stored in the same locations that were used, although for a different state number, at the previous stage. In more visual terms, referring to FIG. 4, the inputs and outputs for each butterfly operation lie at the same positions of the arrays, i.e., the transitions are horizontal.
By selecting the transition with the smaller path metric in the decoder, at each step in time, the number of paths stays constant in the following sense. Half of the entering paths are abandoned, but the surviving paths are appended with both 0 and with 1, creating two paths for each of the surviving paths.
After a sufficient period of time, various paths are abandoned and the number of surviving paths that (at a fixed earlier time t0) pass through a given state becomes ever smaller. Eventually, all of the surviving paths will pass through only a single state and at that time, the decoder can conclude that the most likely information bits are represented by that particular state at time t0.
In implementing a Viterbi decoder, two practical difficulties are present: computational load and the demand for memory. The computational load is more a result of the high symbol rates than of the complexity of the calculation, but a strong incentive still exists to design the algorithms to be as efficient as possible.
The memory demands of a Viterbi decoder derive from the need to maintain an indefinitely long history of the paths surviving to each of the states. Maintaining long histories for each of the 256 states of an IS-95 decoder, for example, can require large amounts of memory. A common solution to the problem of maintaining long histories has been to force the decoder to make decisions prematurely and therefore guarantee a fixed history length. However, such truncations introduce errors and, in order to avoid excessive errors with this approach, history lengths of 4-5 times the constraint length are generally recommended.
Traditional Viterbi decoders, i.e., decoders of convolutionally encoded symbols, record (as a single bit in xe2x80x9ctrace-backxe2x80x9d memory) each decision that is made. At a later time, the decoder must work backward through this historical record, one bit at a time, to determine the final decoded record. This trace-back operation can be computationally intensive.
Often, data is encoded in xe2x80x9cframesxe2x80x9d consisting of a fixed number of bits and with several zero""s added to the end. This procedure allows the decoder to assume that the final state of the frame is zero. Having a known final state greatly simplifies the trace-back problem.
A need has been felt for an apparatus and a method having the feature that the implementation of the decoding of convolutionally encoded symbols is improved. Another feature of the apparatus and method would be that the implementation of the decoding of convolutionally encoded symbols requires less memory. Still another feature of the apparatus and method would permit path trace-back to be performed in units of more than one bit at a time (viz., {constraint_lengthxe2x80x941 } bits at a time). Yet another feature of the apparatus and method would be the decoding of convolutionally encoded symbols in blocks of symbols.
The aforementioned and other features are accomplished, according to the present invention, by providing a unit, hereinafter called a block trellis decoder, that makes decoding decisions determined by the multiple paths entering and exiting from the nodes of a Viterbi trellis diagram. In the present invention, rather than maintain a full history for each node, linked lists of histories are maintained. A procedure for selecting paths based on path metrics is used. Because paths are abandoned at each step, the histories for more distant past events can be compressed to become ever-shorter tables. A set of paths can be summarized in a single file. Each file includes, for each state through which a surviving path passes: a state binary number, the state binary number indicating the set transition history; an index number pointing to a state binary number in the previous file; and a path metric quantity. Forcing the decoder to make premature decisions may still be necessary, but this will be because the total memory describing the transition history has been exhausted. Because this memory is used flexibly and efficiently, forcing premature decision will be necessary less often than when all history back to a fixed point in the past is maintained.